package com.hch.datastructure.simpledemo;

import java.util.ArrayList;

import static java.util.Collections.addAll;

/**
 * @author HeCongHui
 * @date 2022/7/7 10:24
 */
public class QuitSort {

    public ArrayList<Integer> quitSort(ArrayList<Integer> item) {
        //基准条件
        if (item.size() < 2) {
            return item;
        }
        //基准值
        int stand = item.get(0);
        //小于基准数的数组
        ArrayList<Integer> lessArray = new ArrayList<>();
        //大于基准数的数组
        ArrayList<Integer> greaterArray = new ArrayList<>();
        for (int i = 1; i < item.size(); i++) {
            Integer index = item.get(i);
            if (index <= stand) {
                lessArray.add(index);
            } else {
                greaterArray.add(index);
            }
        }
        ArrayList<Integer> newList = new ArrayList<>();
        newList.addAll(quitSort(lessArray));
        newList.add(stand);
        newList.addAll(quitSort(greaterArray));
        return newList;
    }

}
